It is common for a computer processor and associated operating system to have two different levels of resources and protection. One level, referred to as a non-privileged mode or user mode, is used by various operating system components, application programs, and other so-called "user" processes or programs. At this level, an execution thread is prevented by the operating system and by the computer processor from performing certain security-critical operations. The thread is also prevented from directly accessing many system resources. The purpose of the non-privileged execution mode is to isolate a user process as much as possible so that it cannot interfere with other user processes or with operating system functions. While a user process may itself crash, it should not be able to crash other programs or the operating system.
The other level of execution is referred to as privileged mode, system mode, or kernel mode. Critical operating system components are implemented in kernel mode--kernel-mode components are responsible for things like virtual memory management, responding to interrupts and exceptions, scheduling execution threads, synchronizing the activities of multiple processors, and other critical or sensitive functions. Such components, that execute from system mode, are generally referred to collectively as "the kernel."
The kernel is responsible for supervising the virtual memory system in most computer systems. The virtual memory system is largely responsible for isolating processes from each other. With virtual memory, a process is assigned its own virtual address space, which is not available to other processes. Through its virtual memory, a process has a logical view of memory that does not correspond to the actual layout of physical memory. Each time a process uses a virtual memory address, the virtual memory system translates it into a physical address using a virtual-to-physical address mapping contained in some type of look-up structure and address mapping database.
The invention described below arises in the context of computers having privileged and non-privileged execution modes as described above. The invention relates particularly to the use of memory stacks within such computers.
A memory stack is a region of reserved memory in which programs store status data such as procedure and function call return addresses, passed parameters, and local variables. The microprocessor, the program, and the operating system can all maintain one or more separate memory stacks.
Logically, a stack is a memory structure organized as a LIFO (last in, first out) list so that the last data item added to the structure is the first item used. A program can put data onto the stack by executing microprocessor instructions. For example, a "push" instruction typically writes a specified microprocessor register to the stack. A "pop" instruction reads data from the stack. The microprocessor often writes to and reads from the stack automatically in response to certain program flow instructions and other events such as memory faults or interrupts.
As shown in FIG. 1, a memory stack (whether a user memory stack or a kernel memory stack) is typically implemented as a region of virtual memory beginning at a stack base or stack base address. FIG. 1 shows a portion of virtual memory from top to bottom in order of increasing virtual memory addresses. The memory stack is indexed by a pointer referred to as the "stack pointer." When writing to the stack, the microprocessor decrements the stack pointer to the next available address, and then writes the specified data to that address. When reading from the stack, the microprocessor reads from the virtual memory location currently referenced by the stack pointer, and then increments the stack pointer.
Often, memory stacks for user processes are re-sized dynamically, as they become full. That is, virtual memory is allocated and deallocated to the stack to satisfy current memory stack requirements. Guard pages and allocate-on-demand virtual memory are used to accomplish such dynamic allocation and deallocation. A guard page is a reserved page of non-committed virtual memory that bounds the outermost limit of the currently allocated stack memory. In other words, it is a range of virtual addresses into which the stack pointer can be advanced, but for which actual physical memory has not yet been committed. This range of virtual memory is designated as allocate-on-demand memory.
This is illustrated in FIG. 2, which shows a memory stack occupying pages 10 of virtual memory that have been mapped to actual physical memory 12. FIG. 2 also shows a guard page 14, which has not yet been mapped to physical memory. The guard page is designated by the operating system as allocate-on-demand memory.
When a process attempts to access a guard page that has been designated as allocate-on-demand memory, a memory fault is generated. However, the operating system handles allocate-on-demand memory faults in a special way--rather than signaling that an error has occurred, the operating system automatically commits physical memory for the guard page that has been accessed, and reserves another guard page adjacent the newly-allocated virtual memory. These steps are transparent to the executing process--it is able to access the newly allocated stack memory just as if it had always been allocated.
As a variation of this method, some systems reserve a large range of virtual addresses for the stack, placing a guard page at the very end of this range of virtual addresses. The pages preceding the guard page are allocated only as they are accessed, and the guard page stays in a fixed location at the end of the reserved range of addresses.
Multiple memory stacks are usually implemented in a computer. For example, each user process might have one or more memory stacks. When a new user stack is set up, a range of virtual addresses is reserved for use with the new stack. However, only a small amount of physical memory is reserved--additional memory is allocated on an as-needed basis as described above.
The kernel similarly might use several memory stacks. It is highly desirable, in fact, for the kernel to use different stacks than user processes to prevent user processes from interfering with kernel processes. While it would be desirable for kernel memory stacks to be dynamically re-sizable, such a feature has been difficult to implement. One problem is that the kernel itself cannot deal with an allocate-on-demand fault without potentially causing another memory fault. This is because in trying to commit additional memory for a guard page, the kernel would again attempt to use the stack, and in doing so would generate an unrecoverable second fault. Also, it would be fatal for an allocate-on-demand fault to occur in some sections of kernel code in which virtual memory tables and data structures were being manipulated.
At least one operating system (the Windows NT.RTM. operating system) does have provisions for increasing kernel stack sizes in some situations. Specifically, this operating system checks, at certain infrequent places during a thread's execution (when it makes a "callback" to a user program from a kernel function), to ensure that a recursive system call will not exhaust the stack. However, the kernel is still required to use only a fixed amount of stack space during any single recursion--stack re-sizing does not take place dynamically, on an on-going basis.
Because of the limitations noted above, memory stacks used by kernel processes have generally been of fixed size. To avoid memory faults, such memory stacks must be sized large, to accommodate worst-case conditions. In some cases, a design choice is made to limit the size of kernel memory stacks and to restrict kernel code so that it will not exceed allocated stack sizes. The invention described below removes the restrictions on kernel code without the inefficiencies of arbitrarily large kernel stacks.